/*
** 2499.c
** 
** Made by (seakage2h)
** Login   <seakage2h@seakage2h-ubuntu>
** 
** Started on  Sun Sep  7 17:17:18 2008 seakage2h
** Last update Sun May 12 01:17:25 2002 Speed Blue
*/

/* #include "2499.h" */
#include <stdio.h>
#include <stdlib.h>

int gcb_improved(unsigned long int a, unsigned long int b,
		  unsigned long int* l, unsigned long int* r)
{
     div_t tmp;
     if (a == 1){
	  (*r) += (b - a);
	  return 0;
     }
     else if (b == 1){
	  (*l) += (a - b);
	  return 0;
     }
     if (a > b){
	  tmp = div(a, b);
	  (*l) += tmp.quot;
	  a = tmp.rem;
	  return gcb_improved(a, b, l, r);
     }
     else{
	  tmp = div(b, a);
	  (*r)+= tmp.quot;
	  b = tmp.rem;
	  return gcb_improved(a, b, l, r);
     }
}

     
int main()
{
     int instance;
     unsigned long int a, b;
     unsigned long int lc, rc;
     int i;
     
     scanf("%d", &instance);

     /* big loog */
     for(i = 0; i < instance; i++){
	  scanf("%lu%lu", &a, &b);
	  lc = rc = 0;
	  gcb_improved(a, b, &lc, &rc);
	  printf("Scenario #%d:\n", i + 1);
	  printf("%lu %lu\n\n", lc, rc);
     }
     
     return 0;
}
